package java学习.算法.二叉树;

import org.hamcrest.core.Is;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/2 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 树的子结构 {
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }

    /**
     *  判断是否为子树  递归
     *  1. 找到 与子树头结点相同的节点，再开始比较。
     *  2. 找到后，开始逐一比较 头结点、左子树、右子树
     *
     *
     *
     */
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {

        // 有一个为空直接false
        if(root1==null||root2==null){
            return false;
        }
        boolean result = false;

        if (root1.val == root2.val){
            result = IsSon(root1,root2);
        }
        // 头结点不一样，没找到相同节点
        if (result!= true){
//            那是不是左子树的
            result = HasSubtree(root1.left,root2);
        }
        if (result!= true){
//            呃。。。右子树的？？
            result = HasSubtree(root1.right,root2);
        }
//        都不是则返回false
        return result;

    }

//    找到相同节点啦， 开始比较：
    public static boolean IsSon(TreeNode root1, TreeNode root2) {
//        1. 先判空： root2 可以为null
        if (root2 == null) return true;
        if (root1 == null) return false;
//        头结点值不一样： 直接false
        if (root1.val != root2.val){
            return false;
        }

//        判断其左子树、右子树是否一致：
        return IsSon(root1.left,root2.left)&&IsSon(root1.right,root2.right);

    }
}
